package com.berchen.offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。
 */
public class Test11 {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        TreeNode node6=new TreeNode(3);
        TreeNode node10=new TreeNode(2);
        TreeNode node5=new TreeNode(4);
        TreeNode node7=new TreeNode(5);
        TreeNode node9=new TreeNode(12);
        TreeNode node11=new TreeNode(16);
        node6.left=node5;
        node6.right=node7;
//        node10.left=node9;
//        node10.right=node11;
//        root.left=node6;
//        root.right=node10;

        Test11 test11=new Test11();
        System.out.println(test11.Print(root));

    }
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {

        ArrayList<ArrayList<Integer>> result=new ArrayList<>();
        if(pRoot==null){

            return result;
        }
        // 存储每一层的数据
        Queue<TreeNode> node=new LinkedList<>();
        ArrayList<Integer> list=new ArrayList<>();
        list.add(pRoot.val );
        result.add(list);
        if(pRoot.left!=null) {
            node.add(pRoot.left);
        }
        if(pRoot.right!=null) {
            node.add(pRoot.right);
        }

        while (node.size()>0){
            // 用来保存下一层的数据
            Queue<TreeNode> temp=new LinkedList<>();

            ArrayList<Integer> list1=new ArrayList<>();
            while (node.size()>0) {
                TreeNode poll = node.poll();
                list1.add(poll.val);
                if(poll.left!=null) {
                    temp.add(poll.left);
                }
                if(poll.right!=null){
                    temp.add(poll.right);
                }
            }
            result.add(list1);
            // 将下一层数据保存到node中
            node=temp;
        }

        return result;
    }
}
